Progress Report -- Teaching of Procedures

			     by Gerald Jay Sussman



	   The idea of building a programmer is very seductive in that it

   holds the promise of massive bootstrapping and thus ties in with many

   ideas about learning and teaching.  I will avoid going into those issues

   here. It is necessary, however, to explain what I am not working on. I am

   not interested in developing new and better languages for expressing

   algorithms. When FORTRAN was invented, it was touted as an automatic

   programmer, and indeed it was, as it relieved the user of complete

   specification of the details of implementation.  Newer programming

   languages are just elaborations (usually better) of that basic idea. I

   am, however, interested in the problem of implementation of a Partially
   rather than a complete algorithm and a partially   specified algorithm

   specified implementation.  This problem is truly in the domain of

   Artificial Intelligence because the system which "solves" this problem

   needs a great deal of knowledge about the problem domain for which the

   algorithm is being constructed in order to "reasonably" complete the

   specification.   Indeed, a programmer is not told exactly the algorithm

   to be implemented, he is told the problem which his program is expected

   to solve.

	   A programmer hardly ever starts with no program at all. Usually,

   he has a program which is almost but not quite applicable to the need. In

   this case, the programmer determines how the given program is to be

   modified to display the desired behavior; he makes a patch. This





								      PAGE 2
   technique is closely related to debugging, in which a program designed to

   solve a known problem misbehaves in some case. The bug must be understood

   and a patch concocted. In general, under good conditions, the creation of

   a program to solve some problem can be viewed as debugging an existing

   program.

	   Thus, the purpose of this project is to produce a "programmer." I

   am relying deeply on introspective concepts of how I do programming. 


								      PAGE 3


   I. Automatic Program Construction



	   I have been constructing a program called "HACKER" which writes

   and debugs programs in the BLOCKS world. It currently shows signs of

   life, writing some elementary programs by debugging and patching. The

   program HACKER as well as the programs it operates on are written in

   CONNIVER.

	   The physics of the BLOCKS world is as follows: there are blocks

   on a table and a hand. The hand can lift only one block at a time. Hence

   the hand cannot lift a block if there are others on it. A block can only

   be placed on another if there is enough space on the other.  Here we

   introduce one primitive which moves blocks in this world.  (PUTON A B)

   puts block A on block B if A's top is clear and B has space for A on it,

   otherwise it produces an error. HACKER does not consider the structure of

   PUTON just as I don't think about CONS. HACKER does, however, know about

   PUTON and gets the error comments from it when it is incorrectly called.

   HACKER starts out with one well-commented but very limited program to

   work with:



   (IF-NEEDED I-F-ON (IMPERATIVE-FOR (ON !>(X (ATOM !,X)) !>(Y (ATOM !,Y))))

	      (NEEDS (AND (CLEARTOP !,X) (SPACE-FOR !,X !,Y))

		     (PUTON X Y))

	      (ADIEU 'OK))


								      PAGE 4


   This program is called by pattern-directed invocation; if we need an

   imperative for getting atomic object X (not a tower) on an atomic object

   Y, it is called. Its body consists of a call to PUTON commented by its

   prerequisites. The (ADIEU 'OK) informs the caller of success.



   HACKER also knows:



   (IF-NEEDED M-O-CLEARTOP

	   (MEANING-OF (CLEARTOP !'X)

		       (NOT (EXISTS !,(Y (GENSYM))

				      (ON !,Y !,X))))

	   (NOTE))



   i.e. cleartop(x)	 y . . on(y,x)



   (IF-NEEDED S-F-NOT-ON

	   (SUFFICES-FOR (NOT (ON !'X !'Y))

		   (EXISTS !,(Z (GENSYM))

			    (WHERE (ON !,X !,Z) (NOT (= !,Z !,Y)))))

	   (NOTE))



   i.e.     z=y . . on(x,z)    on(x,y)	     /



   Further concepts will be introduced as needed. In section II (Heuristic

   Programming) we will deal with more difficult concepts concerned with


								      PAGE 5


   space.



	   We talk to HACKER by asking it to achieve a desired final state,

   e.g. (ACHIEVE (ON A B)) or, say (ACHIEVE (AND (ON A B) (ON B C))).

   ACHIEVE first tests if its goal is already achieved and if so it returns

   OK.   If not, it searches for a way to accomplish the goal.  

	   Consider (ACHIEVE (ON A B)). If A has a clear top and there is

   space for A on B, then when I-F-ON is invoked, it calls (PUTON 'A 'B)

   which does the job.  Suppose, however, the situation was:



					   (ON A TABLE)

					   (ON B TABLE)

					   (ON C A)



   I-F-ON is invoked, it calls PUTON. PUTON gets angry and returns the error

   comment:

	   UNSATISFIED PREREQUISITE (NOT (ON C A))

   HACKER then backtraces, checking the truth of the comment (NEEDS (AND

   (CLEARTOP ,X) (SPACE-FOR ,X ,Y))...). It finds it untrue. Since this is a

   NEEDS comment, it writes code to achieve the prerequisites and patches it

   in.  Now I-F-ON looks like this:


								      PAGE 6


   (IF-NEEDED I-F-ON (IMPERATIVE-FOR (ON !>(X (ATOM ,X)) !>(Y (ATOM ,Y)))

       (SETUP (CODE-FOR (AND (CLEARTOP !,X) (SPACE-FOR !,X !,Y))

			(PROG "AUX" ((PROTECTEDS NIL))

			      (PROG (ACHIEVE (CLEARTOP !,X))

				    (PROTECT (CLEARTOP !,X)))

			      (PROG (ACHIEVE (SPACE-FOR !,X !,Y))

				    (PROTECT (SPACE-FOR !,X !,Y)))

			      (UNPROTECT PROTECTEDS)))

	      (PUTON X Y)))



   SETUP is a comment explaining the reasons for the code written; to setup

   for (PUTON X Y). CODE-FOR is a comment explaining that its second

   argument was written to achieve the first argument. The code written

   binds a variable PROTECTEDS and initializes it to NIL. It then achieves

   and protects each subgoal, unprotecting them before leaving. Protection

   is a mechanism for catching bugs of interaction between subgoals (to be

   explained later).

	   This code was generated by a process I call pattern-directed

   macro-expansion from a macro in HACKER'S bag of coding tricks. (The

   concepts of a "bag of tricks" is due to Richard Greenblatt). This trick

   is fairly complex and looks like:


								      PAGE 7


   (IF-NEEDED C-F-AND (CODE-FOR (AND . !'L) !<CODE)

       "AUX" ((P NIL))

       (FOR-EACH-ELEMENT G L

	    (CSETQ P (CONS (LIST 'PROG (LIST 'ACHIEVE G)

					(LIST 'PROTECT G))

			     P)))

       (CSETQ CODE (APPEND '(PROG "AUX" ((PROTECTEDS NIL)))

			   (REVERSE P)

			   '((UNPROTECT PROTECTEDS))))

       (NOTE))



   The complexity stems from the ability to code for AND of any number of

   elements.   HACKER then backs up the stack and starts running from

   (SETUP...).   He gets to (ACHIEVE (CLEARTOP !,X)) before running into

   trouble.   (CLEARTOP A) is not true so he looks for an imperative for

   cleartop.   Not finding any he realizes it's time to write some code.

   Finding M-O-CLEARTOP he sees that CLEARTOP is a defined concept and thus

   he writes, by pattern-directed macro-expansion:



   (IF-NEEDED (IMPERATIVE-FOR (CLEARTOP !>X))

	      (MEANING-OF (CLEARTOP !,X)

			 (ACHIEVE (NOT (EXISTS Z1 (ON Z1 !,X)))))

	      (ADIEU 'OK))



								      PAGE 8


   HACKER then runs the new imperative but he needs to achieve the not

   exists expression.  It is not yet true, has no imperative, has no

   explicit meaning, but we  have a trick for this case:



   (IF-NEEDED (CODE-FOR (NOT (EXISTS !>V !'G))

			(FOR-EACH !,V !<G1

				  (ACHIEVE (NOT !<G2))))

	      (CSETQ G1 (SUBST (LIST '/!/; V) V G)

		     G2 (SUBST (LIST '/!/, V) V G))

	      (NOTE))



   Thus we expand the ACHIEVE, patching to get:



   (IF-NEEDED (IMPERATIVE-FOR (CLEARTOP !>X))

	      (MEANING-OF (CLEARTOP !,X)

			  (CODE-FOR (NOT (EXISTS Z1 (ON Z1 !,X)))

				    (FOR-EACH Z1 (ON !Z1 !,X)

					 (ACHIEVE (NOT (ON !,Z1 !,X))))))

	      (ADIEU 'OK))



   FOR-EACH is a canned loop commonly found in CONNIVER programs. This code

   is run until it hits the expression (ACHIEVE (NOT (ON !,Z1 !,X)).  Here

   we expand the macro S-F-NOT-ON getting:



								     PAGE 9


   (IF-NEEDED (IMPERATIVE -FOR (CLEARTOP !X))

       (MEANING-OF (CLEARTOP !,X)

	       (CODE-FOR (NOT (EXISTS Z1 (ON Z1 !,X)))

			 (FOR-EACH Z1 (ON !Z1 !,X)

			     (SUFFICES-FOR (NOT (ON !,Z1 !,X))

				 (ACHIEVE (EXISTS Z2

					     (WHERE (ON !,Z1 !,Z2)

						    (NOT (= !,Z2 !,X))))))

	      (ADIEU 'OK))



   We run this new code until we have to expand the expression (ACHIEVE

   (EXISTS ...)). Here we need the trick:



   (IF-NEEDED (CODE-FOR (EXISTS !V (WHERE !'G !'Q))

	      (PROG "AUX" (!,V)

		    (CHOOSE !,V !,Q (POSSIBLE !,G))

		    (ACHIEVE !,G)))

	      (NOTE))



   Thus we get:


								     PAGE 10


   (IF-NEEDED (IMPERATIVE-FOR (CLEARTOP !X))

       (MEANING-OF (CLEARTOP !,X)

	   (CODE-FOR (NOT (EXISTS Z1 (on Z1 !,X)))

	       (FOR-EACH Z1 (ON !Z1 !,X)

		   (SUFFICES-FOR (NOT (ON !,Z1 !,X))

		       (CODE-FOR (EXISTS Z2 (WHERE (ON !,Z1 !,Z2)

					    (NOT (= !,Z2 !,X))))

				 (PROG "AUX" (Z2)

				       (CHOOSE Z2 (NOT (= !,Z2 !,X))

						  (POSSIBLE (ON !,Z1 !,Z2)))

				       (ACHIEVE (ON !,Z1 !,Z2))))))))

       (ADIEU 'OK))



   This code runs, CHOOSE (by magic of its own) makes Z2=TABLE.  (ACHIEVE

   (ON C TABLE)) (remember Z1=C) finds I-F-ON and calls it recursively,

   solving the problem. 

	   Note that by just running this specific example we get I-F-ON

   patched for situations where X is not CLEARTOP and a completely general

   CLEARTOP routine which not only solves this specific case but also any

   recursively or iteratively complex example.  E.g. the performance program

   can now, without modification achieve (CLEARTOP A) in:




								     PAGE 11


   Note also that the knowledge used in writing this program is divided into

   two independent classes:

	   1) Knowledge of the proglem domain:  

	      I-F-ON, M-O-CLEARTOP, S-F-NOT-ON

	   2) Domain independent programming knowledge: 

	      i.e. all CODE-FOR methods.

   It is my hope and honest belief, that almost all "programming" knowledge

   can be coded into a small number (perhaps 50) coding tricks. New problem

   domain dependent knowledge can be easily added; for instance, I can

   define the concept of a 3-tower as:  



   (IF-NEEDED (MEANING-OF (3-TOWER !'X !'Y !'Z)

			  (AND (ON !,X !,Y) (ON !,Y !,Z))))




								     PAGE 12


   II. Heuristic Programming



	   So far we have been dealing with well-defined and understood

   concepts like CLEARTOP (which even has an explicit definition), NOT-

   ONness (for which we have a sufficient condition) and ONness. The blocks

   world also contains a much fuzzier concept, SPACE-FOR, which we can not

   so clearly work out. For achieving CLEARTOP, there is only one program.

   If it cannot do the job there is no hope. For SPACE-FOR, however, we have

   various strategies which can be tried, no one of which is guaranteed to

   work, nor is the failure of one an indication of ultimate failure. We now

   investigate the methods required to handle such concepts and the

   constructs which are entailed.

	   Suppose that the scene is:



					   (ON A TABLE)

					   (ON B TABLE)

					   (ON C B)



   and we want to put A on B. (CLEARTOP A) is true but we get stuck at

   (SPACE-FOR A B). Since it has no direct route to achieving the goal,

   HACKER looks around for a way to assign blame for this failure. Here we

   introduce a new set of facts.



								     PAGE 13


   (IF-NEEDED M-H-SPACE-FOR-1

      (MAY-HURT (SPACE-FOR !'X !'Y) (CLUTTERED !,Y))

      (NOTE))



   (IF-NEEDED M-O-CLUTTERED

      (MEANING-OF (CLUTTERED !'X)

	     (EXISTS !,(Y (GENSYM)) (WHERE (ON !,Y !,X)

					   (NOT (PROTECTED (ON !,Y !,X))))))

      (NOTE))



   (IF-NEEDED M-H-SPACE-FOR-2

      (∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈∧␈e of C (a heuristic to maximize stability).  This blocks the

   (SPACE-FOR B C) becuase C isn't large enough to hold B with A on its

   middle. What does HACKER do? The performance program is in (STRATEGY-FOR

								     PAGE 19


   (SPACE-FOR B C) ... ) when it discovers that it cannot win by the clutter

   strategy as (ON A C) is protected.  Since there are no other strategies

   currently coded, STRATEGY-FOR asks HACKER for help. HACKER finds another

   strategy, M-H-SPACE-FOR-2; the HAPHAZARD strategy, and finds, indeed,

   that (HAPHAZARD C) is true. This is then coded up as before as an

   alternative strategy: (from now on I will leave out details of expansion,

   filling in with ... and only showing relevant segments.)


   (STRATEGY-FOR (SPACE-FOR !,X !,Y)

      (MEANING-OF (NOT (CLUTTERED !,Y)) ... )

      (MEANING-OF (NOT (HAPHAZARD !,Y)) ... ))



   This code indeed solves the problem but we must introduce some more

   primitives.  



   (IF-NEEDED (IMPERATIVE-FOR (PACKED !X !Y))

      (NEEDS (CLEARTOP !,X) (PACK X Y))

      (ADIEU 'OK))





   (IF-NEEDED (SUFFICES-FOR (NOT (BADLY-PLACED !'X !'Y)) (PACKED !,X !,Y))

      (NOTE))



   Note: STRATEGY-FOR takes any number of strategies and exhausts them in

   the given order.

								     PAGE 20


   Note: PACK pushes its first argument as far as it can from the center of

   its second argument, without falling off.

	   This patch, though it works in this case, and is often useful, is

   not a good patch.  In fact, HACKER realizes the trouble quickly. We see

   that in running the patch, A is pushed to a corner of C. But A was the

   last object moved, (HACKER keeps a record of this) and if an object is

   moved twice with no intervening other manipulations, it should have been

   moved to the correct place the first time. This is not just a matter of

   efficiency -- if the problem had been: (AND (ON A C) (ON D A) (ON B C)

   (ON E B)) we would have had trouble pushing the towers (D A) or (E B).

   Though there is a permutation of the AND which will work, the problem is

   compounded with compound objects (not yet discussed) as in (AND (ON

   (TOWER D A) C) (ON  (TOWER E B) C)). In any case, HACKER has an eye

   peeled (an interrupt set) for double movements in execution of a single

   command. He allows the execution to proceed but leaves a note to himself

   to investigate the problem when the command returns successfully. Each

   time an object is moved, the "physics" leaves a note on the HISTORY list

   with the activation of the mover.  Thus when the program successfully

   returns HACKER sees that the first mover of A was:

   (PUTON A C) called by (ACHIEVE (ON A C))

   and that the second was: (PACK A C) which left A in a good position.

   Thus he edits the first goal to read: (ACHIEVE (ON A C PACK)) which will

   put it down packed the first time (I lied to you about I-F-ON and PUTON:

   they really have an optional position defining argument whose default is

   "center").   


								     PAGE 21


	   The DEBUGGING knowledge appearing in this section is not as

   explicitly stated as in the preceeding sections because it is not yet

   coded. A major criterion for the code is that it break up into BLOCKS and

   programming knowledge.